// kdtree.h
// 04/17/2011: created
#pragma once
#include <vector>
#include <QtCore/QVector>
#include <QtCore/QtAlgorithms>
#include "arma_vector.h"
#include "tree.h"

class BoundingBox 
{
  vec m_min, m_max;
  int n_dim;
public:
  BoundingBox(int dim);

  void accumulate(const vec& v);
  void accumulate(const BoundingBox& b);

  const vec& min() const;
  const vec& max() const;

  double lowerBound(const vec& v) const;
};

class KDTree : public Tree
{
protected:
  typedef Tree::dataset_type    dataset_type;
  typedef std::vector<int>      vint_type;
protected:
  BoundingBox m_box;
  vint_type& m_dimList;
public:
  KDTree(dataset_type& data);
  KDTree(KDTree* parent, int s, int e);
  ~KDTree();
  void buildTree();
  const BoundingBox& box() const { return m_box; }
  int findNN(const vec& query, double& minBound);
  void findKNN(const vec& query, std::vector<int>& knnIdx, std::vector<double>& minBound);
protected:
  int split(int dim);
  static void random_permutation(std::vector<int>& p);
};
